<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="keywords" content="imlgw,半岛铁盒,blog,Java博客,程序员,个人博客,java開發,程序員,個人博客,Java">
    <meta name="description" content="大悲无泪，大悟无言，大笑无声。">
    <meta name="author" content="Resolmi">
    
    <title>
        
            KMP算法及优化 |
        
        Tadow
    </title>
    
<link rel="stylesheet" href="/css/style.css">

    <link rel="shortcut icon" href="https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico">
    <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/css/font-awesome.min.css">
    <script id="hexo-configurations">
    let KEEP = window.KEEP || {};
    KEEP.hexo_config = {"hostname":"imlgw.top","root":"/","language":"zh-CN","path":"search.json"};
    KEEP.theme_config = {"toc":{"enable":true,"number":true,"expand_all":true,"init_open":true},"style":{"primary_color":"#0066CC","avatar":"https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png","favicon":"https://static.imlgw.top/blog/20210731/BtJz541CcmJU.ico","article_img_align":"left","left_side_width":"260px","content_max_width":"920px","hover":{"shadow":false,"scale":true},"first_screen":{"enable":true,"background_img":"/images/image.svg","description":"Keep It Simple & Stupid."},"scroll":{"progress_bar":{"enable":true},"percent":{"enable":true}}},"local_search":{"enable":true,"preload":false},"code_copy":{"enable":true,"style":"default"},"pjax":{"enable":true},"lazyload":{"enable":true},"version":"3.4.3"};
    KEEP.language_ago = {"second":"%s 秒前","minute":"%s 分钟前","hour":"%s 小时前","day":"%s 天前","week":"%s 周前","month":"%s 月前","year":"%s 年前"};
  </script>
<meta name="generator" content="Hexo 5.4.0"><link rel="stylesheet" href="/css/prism.css" type="text/css"></head>


<body>
<div class="progress-bar-container">
    
        <span class="scroll-progress-bar"></span>
    

    
        <span class="pjax-progress-bar"></span>
        <span class="pjax-progress-icon">
            <i class="fas fa-circle-notch fa-spin"></i>
        </span>
    
</div>


<main class="page-container">

    

    <div class="page-main-content">

        <div class="page-main-content-top">
            <header class="header-wrapper">

    <div class="header-content">
        <div class="left">
            
            <a class="logo-title" href="/">
                Tadow
            </a>
        </div>

        <div class="right">
            <div class="pc">
                <ul class="menu-list">
                    
                        <li class="menu-item">
                            <a class=""
                               href="/"
                            >
                                首页
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/archives"
                            >
                                归档
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/categories"
                            >
                                分类
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/sbe"
                            >
                                订阅
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/links"
                            >
                                友链
                            </a>
                        </li>
                    
                        <li class="menu-item">
                            <a class=""
                               href="/about"
                            >
                                关于
                            </a>
                        </li>
                    
                    
                        <li class="menu-item search search-popup-trigger">
                            <i class="fas fa-search"></i>
                        </li>
                    
                </ul>
            </div>
            <div class="mobile">
                
                    <div class="icon-item search search-popup-trigger"><i class="fas fa-search"></i></div>
                
                <div class="icon-item menu-bar">
                    <div class="menu-bar-middle"></div>
                </div>
            </div>
        </div>
    </div>

    <div class="header-drawer">
        <ul class="drawer-menu-list">
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/">首页</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/archives">归档</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/categories">分类</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/sbe">订阅</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/links">友链</a>
                </li>
            
                <li class="drawer-menu-item flex-center">
                    <a class=""
                       href="/about">关于</a>
                </li>
            
        </ul>
    </div>

    <div class="window-mask"></div>

</header>


        </div>

        <div class="page-main-content-middle">

            <div class="main-content">

                
                    <div class="fade-in-down-animation">
    <div class="article-content-container">

        <div class="article-title">
            <span class="title-hover-animation">KMP算法及优化</span>
        </div>

        
            <div class="article-header">
                <div class="avatar">
                    <img src="https://static.imlgw.top/blog/20210731/3C7hCSRR3lfq.png">
                </div>
                <div class="info">
                    <div class="author">
                        <span class="name">Resolmi</span>
                        
                            <span class="author-label">BOSS</span>
                        
                    </div>
                    <div class="meta-info">
                        <div class="article-meta-info">
    <span class="article-date article-meta-item">
        <i class="fas fa-edit"></i>&nbsp;2018-09-06 00:00:00
    </span>
    
        <span class="article-categories article-meta-item">
            <i class="fas fa-folder"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/categories/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    
    
        <span class="article-tags article-meta-item">
            <i class="fas fa-tags"></i>&nbsp;
            <ul>
                
                    <li>
                        <a href="/tags/%E7%AE%97%E6%B3%95/">算法</a>&nbsp;
                    </li>
                
                    <li>
                        | <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>&nbsp;
                    </li>
                
            </ul>
        </span>
    

    
    
        <span class="article-wordcount article-meta-item">
            <i class="fas fa-file-word"></i>&nbsp;<span>2.1k 字</span>
        </span>
    
    
        <span class="article-min2read article-meta-item">
            <i class="fas fa-clock"></i>&nbsp;<span>8 分钟</span>
        </span>
    
    
        <span class="article-pv article-meta-item">
            <i class="fas fa-eye"></i>&nbsp;<span id="busuanzi_value_page_pv"></span>
        </span>
    
</div>

                    </div>
                </div>
            </div>
        

        <div class="article-content markdown-body">
            <h2 id="KMP算法及优化"><a href="#KMP算法及优化" class="headerlink" title="KMP算法及优化"></a>KMP算法及优化</h2><blockquote>
<p>后面有时间再来重写一下，kmp还是挺重要的</p>
</blockquote>
<p>KMP算法是一种改进的<a class="link"   target="_blank" rel="noopener" href="https://baike.so.com/doc/9018958-9348545.html" >字符串匹配<i class="fas fa-external-link-alt"></i></a>算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特–莫里斯–普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。<br> 开发环境   : sublime+MinGW </p>
<ul>
<li>暴力匹配法</li>
</ul>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="comment">//暴力匹配   </span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">BruteForce</span><span class="params">(String S, String T,<span class="keyword">int</span> begin)</span></span>&#123; </span><br><span class="line">	<span class="keyword">int</span> i=begin,j=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(i&lt;S.length&amp;&amp;j&lt;T.length)&#123;</span><br><span class="line">		<span class="keyword">if</span>(S.str[i]==T.str[j])&#123;</span><br><span class="line">			j++;</span><br><span class="line">			i++;</span><br><span class="line">		&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">			<span class="comment">//母串的当前位置+1向后移动</span></span><br><span class="line">			i=i-j+<span class="number">1</span>;</span><br><span class="line">			<span class="comment">//子串从0开始</span></span><br><span class="line">			j=<span class="number">0</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (i&lt;s(S.length-T.length))</span><br><span class="line">		<span class="keyword">return</span> i-j-begin;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">-1</span>;  <span class="comment">//没找到</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>暴力匹配比较简单粗暴，就是一个个的比对如果不对母串就回溯直到配成功。<br>这个算法无疑时间复杂度较高，最糟糕情况为 O(m*n);而这个算法的缺陷就在于每次母串的不必要的回溯，于是KMP算法出现了</p>
<ul>
<li>KMP算法</li>
</ul>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">getNext</span><span class="params">(String S,<span class="keyword">int</span> next[])</span></span>&#123;</span><br><span class="line">	<span class="comment">//自己和自己匹配其实和kmp是一个道理</span></span><br><span class="line">	<span class="keyword">int</span> i=<span class="number">1</span>,j=<span class="number">0</span>;</span><br><span class="line">	<span class="comment">//和标准的KMP不台一样,标准的KMP是从1开始的其实原理也一样，这样更习惯</span></span><br><span class="line">	next[<span class="number">0</span>]=<span class="number">-1</span>;</span><br><span class="line">	next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">	<span class="comment">//循环 n-2 次</span></span><br><span class="line">	<span class="keyword">while</span>(i&lt;S.length<span class="number">-1</span>)&#123;</span><br><span class="line">		<span class="keyword">if</span>(S.str[i]==S.str[j])&#123;</span><br><span class="line">			++j;</span><br><span class="line">			++i;</span><br><span class="line">			next[i]=j;</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(j==<span class="number">0</span>)&#123;</span><br><span class="line">			<span class="comment">//如果和前缀第一个字符就不等，i后移下一个位置的next为0</span></span><br><span class="line">			++i;</span><br><span class="line">			next[i]=<span class="number">0</span>;</span><br><span class="line">		&#125;<span class="keyword">else</span></span><br><span class="line">		    <span class="comment">//j回退到之前的位置</span></span><br><span class="line">			j=next[j];</span><br><span class="line">	&#125;</span><br><span class="line">&#125; </span><br><span class="line"></span><br><span class="line"><span class="comment">//返回第一次出现的位置</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">KMP</span><span class="params">(String S,String T,<span class="keyword">int</span> begin)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i=begin,j=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">int</span> next[<span class="number">100</span>];</span><br><span class="line">	getNext(T,next);</span><br><span class="line">	<span class="keyword">while</span>(i&lt;S.length&amp;&amp;j&lt;T.length)&#123;</span><br><span class="line">		<span class="keyword">if</span>(S.str[i]==T.str[j])&#123;</span><br><span class="line">			++i;</span><br><span class="line">			++j;</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(j==<span class="number">0</span>)&#123;</span><br><span class="line">			i++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">		&#123;</span><br><span class="line">		 j=next[j];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span> (i&lt;s(S.length-T.length))</span><br><span class="line">		<span class="keyword">return</span> i-j-begin;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">-1</span>;   <span class="comment">//没找到</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这个算法的原理其实很好理解 ,母串不回溯，如果不相等字串就会跳到对应的位置继续比对</p>
<h1 id="a-b-a-b-c"><a href="#a-b-a-b-c" class="headerlink" title="a b a b c"></a>a b a b c</h1><h1 id="a-b-c"><a href="#a-b-c" class="headerlink" title="a b c"></a>a b c</h1><p>比如上面这种，c和a不相等 ，如果是暴力匹配那母串就会回溯到第二个字符b的位置继续比对，但是这并没有意义，因为子串的字符都不相等，正确的做法肯定是直接将字串右滑，或者说将子串回溯，回溯到a的位置，然后计较母串的第三个字符和子串的第一个字符…… 分析一下可以看出来这个算法最坏时间复杂度为O(n+m)<br>那么问题来了回溯的位置如何确定？这也是这个算法的关键之处。要得到一个对应每个位置的next数组储存当失配时回溯的位置，这个数组的确定只和子串本身的结构有关其代表的时最长的公共前后缀的长度，关于next数组的求法就不说了，人眼基本上一眼就能看出来。</p>
<ul>
<li>next数组编程实现</li>
</ul>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">getNext</span><span class="params">(String S,<span class="keyword">int</span> next[])</span></span>&#123;</span><br><span class="line">	<span class="comment">//自己和自己匹配其实和kmp是一个道理</span></span><br><span class="line">	<span class="keyword">int</span> i=<span class="number">1</span>,j=<span class="number">0</span>;</span><br><span class="line">	<span class="comment">//和标准的KMP不台一样,标准的KMP是从1开始的其实原理也一样，这样更习惯</span></span><br><span class="line">	next[<span class="number">0</span>]=<span class="number">-1</span>;</span><br><span class="line">	next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">	<span class="comment">//循环 n-2 次</span></span><br><span class="line">	<span class="keyword">while</span>(i&lt;S.length<span class="number">-1</span>)&#123;</span><br><span class="line">		<span class="keyword">if</span>(S.str[i]==S.str[j])&#123;</span><br><span class="line">			++j;</span><br><span class="line">			++i;</span><br><span class="line">			next[i]=j;</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(j==<span class="number">0</span>)&#123;</span><br><span class="line">			<span class="comment">//如果和前缀第一个字符就不等，i后移下一个位置的next为0</span></span><br><span class="line">			++i;</span><br><span class="line">			next[i]=<span class="number">0</span>;</span><br><span class="line">		&#125;<span class="keyword">else</span></span><br><span class="line">		    <span class="comment">//j回退到之前的位置</span></span><br><span class="line">			j=next[j];</span><br><span class="line">	&#125;</span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure>
<p>一开始看到这个我是比较懵的怎么这么短？仔细看了下这几行代码前面的其实都还好理解,相当于自己和自己匹配</p>
<h1 id="！！！关键是后面的不相等的情况"><a href="#！！！关键是后面的不相等的情况" class="headerlink" title="！！！关键是后面的不相等的情况"></a>！！！关键是后面的不相等的情况</h1><p>这里我也纠结了小半天随后在网上看到了一个图讲解这个的瞬间就开朗了这里就直接搬过来了（对<a class="link"   target="_blank" rel="noopener" href="https://blog.csdn.net/qq_30974369/article/details/74276186" >原文<i class="fas fa-external-link-alt"></i></a>加了一点自己的直观理解并另外加上了参考《大话数据结构》里面的对于KMP算法的优化）</p>
<h1 id="a-b-a-c-f-g-a-b-a-b-h"><a href="#a-b-a-c-f-g-a-b-a-b-h" class="headerlink" title="a b  a  c  f  g a  b a b h"></a>a b  a  c  f  g a  b a b h</h1><p><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://p1.cdn.img9.top/ipfs/QmQLpe9fWukFT9is6XnAmmAyBdTCVYSeV6oj7mn5yGVsy8?1.png"
                      alt="image"
                ></p>
<h1 id="a-b-a-c-f-g-a-b-a-b-h-1"><a href="#a-b-a-c-f-g-a-b-a-b-h-1" class="headerlink" title="a b  a  c  f  g a  b a b  h"></a><strong>a b  a</strong>  c  f  g <strong>a  b a</strong> <em>b</em>  h</h1><p>红色的是当前匹配上的最长的前后缀，蓝色为当前匹配位置，也就是<em>i</em> 的位置 与上面对应的就是b 的位置了<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://p3.cdn.img9.top/ipfs/QmaFp1PaEY5Ednc4wUdLatsuJ7e4fibKv7jXwroGGb8rXN?3.png"
                      alt="image2"
                ></p>
<h1 id="a-b-a-c-f-g-a-b-a-b-h-2"><a href="#a-b-a-c-f-g-a-b-a-b-h-2" class="headerlink" title="a b  a  c  f  g a  b  a b  h"></a><strong>a b  a</strong>  <em>c</em>  f  g <strong>a  b  a</strong> <em>b</em>  h</h1><p>绿色为当前匹配到的最长前缀的后一位也就是 <em>j</em>  的位置 对应 c 的位置<br>显然c b不相等  如果不相等那就不能继续往后找了 那像 aba 这么长的公共前后缀就用不了了，也就是你的next数组会变小，前后缀相似度会减小。<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://p1.cdn.img9.top/ipfs/QmURa6y33pwvpWjoBZ6eSiyZzraBd9QPWSBF13gq2xdPnT?1.png"
                      alt="image3"
                ><br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://p2.cdn.img9.top/ipfs/QmVfW9VQ2JYhNigxskotFVRtgAYcEhksBBEKzSztKn3p9b?2.png"
                      alt="image4"
                ></p>
<h1 id="a-b-a-c-f-g-a-b-a-b-h-3"><a href="#a-b-a-c-f-g-a-b-a-b-h-3" class="headerlink" title="a  b  a  c  f  g  a  b  a b  h"></a><strong>a</strong>  <em>b</em>  <strong>a</strong>  c  f  g  <strong>a</strong>  b  <strong>a</strong> b  h</h1><p>如图四块灰色区域完全相等，关键步骤 j=next[j];之前的j在绿色区域 现在的 j 回溯到了紫色区域 也就是对应b的位置<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://p1.cdn.img9.top/ipfs/QmYo2cscPKdCL9tGGn2frfrn6p4WuGXuma6W6yQSEw4bdx?1.png"
                      alt="image5"
                ><br>相信到这里应该就看明白了,四块区域相等，如果蓝色部分和紫色相等是不是就又有了公共的前后缀了呢？那如果不同就会继续递推。</p>
<ul>
<li>KMP优化<br>什么？这么吊的算法还可以优化？的确，KMP还可以优化，这里直接拿《大话数据结构》里面的例子来说明 (ps : 这里大话数据结构和KMP原始的是一样的，也就是next是从1开始的，我是从0开始的)<br><img  
                     lazyload
                     src="/images/loading.svg"
                     data-src="https://p0.cdn.img9.top/ipfs/QmSum26wHswwEgRmR79oM75o8afbAMCy2ZMQcremrXpfka?0.png"
                      alt="image6"
                >    <ul>
<li>next优化</li>
</ul>
</li>
</ul>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">getNexval</span><span class="params">(String S,<span class="keyword">int</span> next[])</span></span>&#123;</span><br><span class="line">	<span class="comment">//自己和自己匹配其实和kmp是一个道理</span></span><br><span class="line">	<span class="keyword">int</span> i=<span class="number">1</span>,j=<span class="number">0</span>;</span><br><span class="line">	<span class="comment">//和标准的KMP不台一样,标准的KMP是从1开始的其实原理也一样，这样更习惯</span></span><br><span class="line">	next[<span class="number">0</span>]=<span class="number">-1</span>;</span><br><span class="line">	next[<span class="number">1</span>]=<span class="number">0</span>;</span><br><span class="line">	<span class="comment">//循环n-2次</span></span><br><span class="line">	<span class="keyword">while</span>(i&lt;S.length<span class="number">-1</span>)&#123;</span><br><span class="line">		<span class="keyword">if</span>(S.str[i]==S.str[j])&#123;</span><br><span class="line">			++j;</span><br><span class="line">			++i;</span><br><span class="line">			<span class="comment">//下一对对应的位置（也就是正在求next值的位置）</span></span><br><span class="line">			<span class="keyword">if</span>(S.str[j]==S.str[i])&#123;</span><br><span class="line">				<span class="comment">//这一步实际上是跳过了重复的部分 如果和这个位置的next值的字符相同就可以将这个位置的next字符设置为next位置字符的next值</span></span><br><span class="line">				next[i]=next[j];</span><br><span class="line">			&#125;<span class="keyword">else</span></span><br><span class="line">			next[i]=j;</span><br><span class="line">		&#125;<span class="keyword">else</span> <span class="keyword">if</span>(j==<span class="number">0</span>)&#123;</span><br><span class="line">			<span class="comment">//如果和前缀第一个字符就不等，i后移下一个位置的next为0</span></span><br><span class="line">			++i;</span><br><span class="line">			next[i]=<span class="number">0</span>;</span><br><span class="line">		&#125;<span class="keyword">else</span></span><br><span class="line">		    <span class="comment">//j回退到之前的位置</span></span><br><span class="line">			j=next[j];</span><br><span class="line">	&#125;</span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure>
<p>其实优化的理由就是在进行和子串匹配的时候如果失配，在子串回溯时回溯到的那个值和当前的值相同那么我们可以直接回溯到 那个回溯值的回溯值，可能有点绕但是仔细想想就明白了。</p>
<h1 id="a-b-a-b-a-a-a-b-a"><a href="#a-b-a-b-a-a-a-b-a" class="headerlink" title="a b a b a a a b a"></a><strong>a b a b a a a b a</strong></h1><p>这个字符串的next应该是 next=[-1,0,0,1,2,3,1,1,2]<br>nextval=[-1,0,0,0,0,3,1,0,0] （这里有一个小问题，那就是前两位是不用考虑的，永远是-1 0，所以如果按照上面的说法可能会认为第三个是-1，其实不是的具体的可以看代码，如果时官方的那种从1开始就没有这种顾虑）。<br>拿这个实际的来说 ,  <strong>a b a b a a a b a</strong>当比对到该子串最后一个a时 不相等 ，按照之前的方法回溯，回溯到index=2的a位置，发现这货也是a那肯定也不相等，然后又回溯回溯到第一个a，这中间不就多回溯了一次么？为什么不一次到位呢？所以我们直接判断将要回溯的值和当前值是不是相等，相等就把将要回溯的值的回溯值赋给当前值。</p>

        </div>

        
            <div class="post-copyright-info">
                <div class="article-copyright-info-container">
    <ul>
        <li>本文标题：KMP算法及优化</li>
        <li>本文作者：Resolmi</li>
        <li>创建时间：2018-09-06 00:00:00</li>
        <li>
            本文链接：https://imlgw.top/2018/09/06/4d30a252/
        </li>
        <li>
            版权声明：本博客所有文章除特别声明外，均采用 <a class="license" target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">BY-NC-SA</a> 许可协议。转载请注明出处！
        </li>
    </ul>
</div>

            </div>
        

        
            <div class="article-nav">
                
                    <div class="article-prev">
                        <a class="prev"
                           rel="prev"
                           href="/2018/09/24/bea4831e/"
                        >
                            <span class="left arrow-icon flex-center">
                              <i class="fas fa-chevron-left"></i>
                            </span>
                            <span class="title flex-center">
                                <span class="post-nav-title-item">Spring-Redis遇到的bug</span>
                                <span class="post-nav-item">上一篇</span>
                            </span>
                        </a>
                    </div>
                
                
                    <div class="article-next">
                        <a class="next"
                           rel="next"
                           href="/2018/08/18/680ae0e/"
                        >
                            <span class="title flex-center">
                                <span class="post-nav-title-item">双向循环链表</span>
                                <span class="post-nav-item">下一篇</span>
                            </span>
                            <span class="right arrow-icon flex-center">
                              <i class="fas fa-chevron-right"></i>
                            </span>
                        </a>
                    </div>
                
            </div>
        

        
            <div class="comment-container">
                <div class="comments-container">
    <div id="comment-anchor"></div>
    <div class="comment-area-title">
        <i class="fas fa-comments">&nbsp;评论</i>
    </div>
    

        
            <section class="disqus-comments">
<div id="disqus_thread">
  <noscript>Please enable JavaScript to view the <a target="_blank" rel="noopener" href="//disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
</div>
</section>

<script>
var disqus_shortname = 'imlgw';

var disqus_url = 'https://imlgw.top/2018/09/06/4d30a252/';

(function(){
  var dsq = document.createElement('script');
  dsq.type = 'text/javascript';
  dsq.async = true;
  dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
  (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>

<script id="dsq-count-scr" src="//imlgw.disqus.com/count.js" async></script>
        
    
</div>

            </div>
        
    </div>
</div>


                
            </div>

        </div>

        <div class="page-main-content-bottom">
            <footer class="footer">
    <div class="info-container">
        <div class="copyright-info info-item">
            &copy;
            
              <span>2018</span>&nbsp;-&nbsp;
            
            2021&nbsp;<i class="fas fa-heart icon-animate"></i>&nbsp;<a href="/">Resolmi</a>
        </div>
        
            <script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
            <div class="website-count info-item">
                
                    <span id="busuanzi_container_site_uv">
                        访问人数&nbsp;<span id="busuanzi_value_site_uv"></span>&ensp;
                    </span>
                
                
                    <span id="busuanzi_container_site_pv">
                        总访问量&nbsp;<span id="busuanzi_value_site_pv"></span>
                    </span>
                
            </div>
        
        
            <div class="icp-info info-item"><a target="_blank" rel="nofollow" href="https://beian.miit.gov.cn">鄂ICP备18011208号</a></div>
        
    </div>
</footer>

        </div>
    </div>

    
        <div class="post-tools">
            <div class="post-tools-container">
    <ul class="tools-list">
        <!-- TOC aside toggle -->
        
            <li class="tools-item page-aside-toggle">
                <i class="fas fa-outdent"></i>
            </li>
        

        <!-- go comment -->
        
            <li class="go-comment">
                <i class="fas fa-comment"></i>
            </li>
        
    </ul>
</div>

        </div>
    

    <div class="right-bottom-side-tools">
        <div class="side-tools-container">
    <ul class="side-tools-list">
        <li class="tools-item tool-font-adjust-plus flex-center">
            <i class="fas fa-search-plus"></i>
        </li>

        <li class="tools-item tool-font-adjust-minus flex-center">
            <i class="fas fa-search-minus"></i>
        </li>

        <li class="tools-item tool-expand-width flex-center">
            <i class="fas fa-arrows-alt-h"></i>
        </li>

        <li class="tools-item tool-dark-light-toggle flex-center">
            <i class="fas fa-moon"></i>
        </li>

        <!-- rss -->
        

        

        <li class="tools-item tool-scroll-to-bottom flex-center">
            <i class="fas fa-arrow-down"></i>
        </li>
    </ul>

    <ul class="exposed-tools-list">
        <li class="tools-item tool-toggle-show flex-center">
            <i class="fas fa-cog fa-spin"></i>
        </li>
        
            <li class="tools-item tool-scroll-to-top flex-center">
                <i class="arrow-up fas fa-arrow-up"></i>
                <span class="percent"></span>
            </li>
        
    </ul>
</div>

    </div>

    
        <aside class="page-aside">
            <div class="post-toc-wrap">
    <div class="post-toc">
        <ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#KMP%E7%AE%97%E6%B3%95%E5%8F%8A%E4%BC%98%E5%8C%96"><span class="nav-number">1.</span> <span class="nav-text">KMP算法及优化</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-a-b-c"><span class="nav-number"></span> <span class="nav-text">a b a b c</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-c"><span class="nav-number"></span> <span class="nav-text">a b c</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#%EF%BC%81%EF%BC%81%EF%BC%81%E5%85%B3%E9%94%AE%E6%98%AF%E5%90%8E%E9%9D%A2%E7%9A%84%E4%B8%8D%E7%9B%B8%E7%AD%89%E7%9A%84%E6%83%85%E5%86%B5"><span class="nav-number"></span> <span class="nav-text">！！！关键是后面的不相等的情况</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-a-c-f-g-a-b-a-b-h"><span class="nav-number"></span> <span class="nav-text">a b  a  c  f  g a  b a b h</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-a-c-f-g-a-b-a-b-h-1"><span class="nav-number"></span> <span class="nav-text">a b  a  c  f  g a  b a b  h</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-a-c-f-g-a-b-a-b-h-2"><span class="nav-number"></span> <span class="nav-text">a b  a  c  f  g a  b  a b  h</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-a-c-f-g-a-b-a-b-h-3"><span class="nav-number"></span> <span class="nav-text">a  b  a  c  f  g  a  b  a b  h</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#a-b-a-b-a-a-a-b-a"><span class="nav-number"></span> <span class="nav-text">a b a b a a a b a</span></a>
    </div>
</div>
        </aside>
    

    <div class="image-viewer-container">
    <img src="">
</div>


    
        <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
          <span class="search-input-field-pre">
            <i class="fas fa-keyboard"></i>
          </span>
            <div class="search-input-container">
                <input autocomplete="off"
                       autocorrect="off"
                       autocapitalize="off"
                       placeholder="搜索..."
                       spellcheck="false"
                       type="search"
                       class="search-input"
                >
            </div>
            <span class="popup-btn-close">
                <i class="fas fa-times"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fas fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>

    

</main>



<script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/utils.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/main.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/header-shrink.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/back2top.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/dark-light-toggle.js"></script>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/local-search.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/code-copy.js"></script>



    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/lazyload.js"></script>


<div class="post-scripts pjax">
    
        <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/left-side-toggle.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/anime.min.js"></script><script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/toc.js"></script>
    
</div>


    <script src="//cdn.jsdelivr.net/npm/hexo-theme-keep@3.4.3/source/js/libs/pjax.min.js"></script>
<script>
    window.addEventListener('DOMContentLoaded', () => {
        window.pjax = new Pjax({
            selectors: [
                'head title',
                '.page-container',
                '.pjax'
            ],
            history: true,
            debug: false,
            cacheBust: false,
            timeout: 0,
            analytics: false,
            currentUrlFullReload: false,
            scrollRestoration: false,
            // scrollTo: true,
        });

        document.addEventListener('pjax:send', () => {
            KEEP.utils.pjaxProgressBarStart();
        });

        document.addEventListener('pjax:complete', () => {
            KEEP.utils.pjaxProgressBarEnd();
            window.pjax.executeScripts(document.querySelectorAll('script[data-pjax], .pjax script'));
            KEEP.refresh();
        });
    });
</script>



<script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.x/lib/L2Dwidget.min.js"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"https://cdn.jsdelivr.net/npm/live2d-widget-model-hijiki@1.0.5/assets/hijiki.model.json"},"display":{"superSample":2,"width":160,"height":320,"position":"right","hOffset":0,"vOffset":-70},"mobile":{"show":false,"scale":0.2},"log":false});</script></body>
</html>
